【算法】【数组与矩阵模块】自然数组排序（空间O(1)） |
您所在的位置：网站首页 › numpy nparray › 【算法】【数组与矩阵模块】自然数组排序（空间O(1)） |
|
目录
前言问题介绍解决方案代码编写java语言版本c语言版本c++语言版本
思考感悟写在最后
前言
当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识！ 问题介绍原问题 给定自然数组，长度为n，数组中的数属于 [1…n]且不相同，将此数组排序，要求空间O（1） 如： arr = [1,3,2] 排序后： arr = [1,2,3] 解决方案原问题： 方法一：交换法 1、从遍历arr中的每一个数，判断每一个数是否在自己应该在的位置上，如果是，则下一个 2、如果不是，则将当前位置记为cur，循环查找cur应该在的位置，当cur在应该在的位置时为止 方法二：替换法 1、从遍历arr中的每一个数，判断每一个数是否在自己应该在的位置上，如果是，则下一个 2、如果不是，则当前位置值记为cur，找到cur应该在的位置，cur与当前位置进行值交换，继续循环， 直到 cur应该在的位置是当前位置为止。 代码编写 java语言版本原问题： 方法一: /** * 方法一： * 替换 * @param array */ public static void sort1(int[] array){ try { int tem = 0; for (int i = 0; i int index = array[i] - 1; tem = array[index]; array[index] = array[i]; array[i] = tem; } } }catch (Exception e){ e.printStackTrace(); } }方法二： /** * 方法二：有点不好理解 * 将要被替换的值保存起来，while里面不能出现i，因为i不会变， * 一直循环替换直到替换到array[i]正确为止 * @param array */ public static void sort2(int[] array){ try { int tem = 0; int next = 0; for (int i = 0; i // 要被替换的数字 next = array[tem-1]; array[tem-1] = tem; tem = next; } } }catch (Exception e){ e.printStackTrace(); } } c语言版本正在学习中 c++语言版本正在学习中 思考感悟这道题其实考察一个数组的交换能力，刚开始我写的时候思路比较混乱，但是理清楚的就简单了，这两个方法其实都一样，都需要一块内存存储“被换出来”的那个数，只不过方法一用了数组中的内存，方法二使用了外部的一块内存，总体来讲，时间复杂度不变，空间复杂度因为要交换，所以需要一块临时内存，大家都一样。 写在最后方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~ 如果需要git源码可邮件给[email protected] 再次感谢左大神对我算法的指点迷津！ |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |